package ch2.link.single;

/**
 * 例2.16：有两个递增有序整数单链表A和B，设计一个算法采用二路归并方法将A和B的所有数据结点合并到递增有序单链表C中。
 * 要求算法的空间复杂度为O(1)。
 */
public class Exam2_16 {
    public static LinkListClass<Integer> Merge(LinkListClass<Integer> A,
                                                LinkListClass<Integer> B) { //例2.16的算法
        // 1. 初始化
        LinkListClass<Integer> C = new LinkListClass<>();
        LinkNode<Integer> p = A.head.next;      //p指向A的首结点
        LinkNode<Integer> q = B.head.next;      //q指向B的首结点
        LinkNode<Integer> t = C.head;           //t为C的尾结点
        // 2. 循环遍历A、B相同长度的元素，用尾插法加到链表
        while (p != null && q != null) {
            // 2.1 A的元素值小于B的元素的值，则把A的元素加到C
            if (p.data < q.data) {
                t.next = p;
                t = p;
                p = p.next;
            } else {
                t.next = q;
                t = q;
                q = q.next;
            }
        }
        t.next = null;      //尾结点next置空
        // 3. A或B多出来的元素，追加到C的后面
        if (p != null) {
            t.next = p;
        }else if (q != null) {
            t.next = q;
        }
        // 4. 返回链表C
        return C;
    }

    public static void main(String[] args) {
        // 1. 根据一个整型数组创建一个单链表A、B
        Integer[] a = {1, 3, 5, 7};
        LinkListClass<Integer> A = new LinkListClass<>();
        A.CreateListR(a);
        System.out.println("A: " + A);

        Integer[] b = {1, 2, 5, 7, 9, 10, 20};
        LinkListClass<Integer> B = new LinkListClass<>();
        B.CreateListR(b);
        System.out.println("B: " + B);
        // 2. 合并A、B得到C
        System.out.println("二路归并");
        LinkListClass<Integer> C = Exam2_16.Merge(A, B);
        System.out.println("C: " + C);
        System.out.println("B: " + B);
        System.out.println("A: " + A);
    }
}

